#define _CRT_SECURE_NO_WARNINGS 1


typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->top = 0;
	p->capacity = 0;
}

void STPush(ST* p, STDataType x)
{
	if (p->top == p->capacity)
	{
		int newsize = p->top == 0 ? 4 : p->capacity * 2;
		STDataType* newspace = (STDataType*)realloc(p->a, sizeof(STDataType) * newsize);
		if (newspace == NULL)
		{
			perror("realloc fail");
			return;
		}
		p->a = newspace;
		p->capacity = newsize;
	}
	p->a[p->top] = x;
	p->top++;
}

bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

void STPop(ST* p)
{
	assert(p);
	assert(!STEmpty(p));

	p->top--;
}

STDataType STTop(ST* p)
{
	assert(p);
	assert(!STEmpty(p));

	return p->a[p->top - 1];
}

int STSize(ST* p)
{
	assert(p);
	assert(!STEmpty(p));

	return p->top;
}

void STDestroy(ST* p)
{
	assert(p);

	free(p->a);
	p->a == NULL;
	p->capacity = p->top = 0;
}

bool isValid(char* s)
{
	ST pst;
	STInit(&pst);
	while (*s)
	{
		if (*s == '(' || *s == '[' || *s == '{')
		{
			STPush(&pst, *s);
		}
		else
		{
			if (STEmpty(&pst))
			{
				STDestroy(&pst);
				return false;
			}
			char top = STTop(&pst);
			STPop(&pst);
			if (*s == ')' && top != '(' || *s == ']' && top != '[' || *s == '}' && top != '{')
			{
				STDestroy(&pst);
				return false;
			}
		}
		s++;
	}
	bool ret = STEmpty(&pst);
	STDestroy(&pst);
	return ret;
}